The present invention relates generally to the field of content addressable memories (CAMs) and more particularly to a circuit and method for reducing power usage during search operations in a CAM.
A CAM is a memory device in which data is accessed and modified based on the content of the stored data, rather than the location where the data is stored. In general, a typical CAM search operation involves receiving a search data word and comparing the search data word with all entries in the CAM to determine whether there exists a single match, a multiple match or a mismatch between the search data word and entries in the CAM. Each storage location in a row of a CAM is connected to a matchline that indicates a match or mismatch result of the comparison between the stored data word and the search word. All match lines indicating a match condition are typically processed by a priority encoder (PE) to determine a highest priority match address which is provided as an output of the CAM.
Each data word and match line combination has a unique N-bit address within the CAM. Accordingly, for any search cycle there may be up to 2N match lines activated. The priority encoder is coupled to the match lines and generates an N-bit address corresponding to the highest priority active match line. This N-bit address may then be used, for example, as a pointer in an Internet Protocol (IP) routing table lookup, compression and decompression or fully associative cache memory implementations in microprocessor systems. Ternary CAMs are widely used in networking applications due to their ability to store logic xe2x80x9c1xe2x80x9d, logic xe2x80x9c0xe2x80x9d as well as xe2x80x9cdon""t carexe2x80x9d states. There is an ever increasing demand for wider data width CAMSs. CAMs are commonly available in data widths (denoted by M) that are 72-bits and 144-bits and more recently 288-bits wide.
With increasing data widths, power or current consumption during search operations in the CAM becomes increasingly important. The reason for this may be explained as follows.
In a search operation, data is provided to the CAM for comparing to stored data. The CAM cells are normally designed such that a match between search data and stored data provides a non-conductive path, whereas a mis-match provides a conductive path. A row of CAM consists of cells coupled in parallel between common nodes called a match line (ML) and a tail line (TL). Each individual ML connects to M cells (where M is the number of bits or usually the data width). Typically, in a search operation, M-bit search data is provided to a search data path which consists of M search lines coupled to corresponding columns of CAM cells. All N-rows of the CAM simultaneously then compare the search data with the stored data in each cell-typically implemented as an exclusive-OR comparison block-and provide a result of his comparison to each match line associated with each row of the CAM. The result on the match line is then sensed, amplified and typically latched in order to provide a logic level result of the search operation.
There are two main sources of substantial power consumption during search operations in CAM""s: power consumed by match lines and power consumed by search lines. Conventionally, all match lines are precharged to a logic xe2x80x98Hxe2x80x99 state (a match condition), and then the comparison with search data is allowed to pull match lines to a logic xe2x80x98Lxe2x80x99 state (a miss condition).
In most CAM applications xe2x80x9cmissesxe2x80x9d occur more frequently than xe2x80x9chitsxe2x80x9d. Precharging match lines to a logic xe2x80x98Hxe2x80x99 and discharging match lines to logic xe2x80x98Lxe2x80x99 for misses tends to generate high power consumption due to the high current associated with charging and discharging all match lines for each search operation. In additions with an increased number of cells connected to each match line for wider-word CAM applications, the capacitance of match lines increases accordingly, which in turn increases the current required to charge and discharge the match lines.
Various solutions have been proposed for reducing the power consumed during search operations, such as segmenting match lines into multiple segments and activating segments sequentially based on match or miss results of previous segments,
For example, a segmented match line architecture is described in U.S. Pat. No. 6,243,280 (Wong et al.)., wherein rows of the CAM are partitioned into a plurality of segments. For each match line, the first of the plurality of match line segments is precharged and a search operation is performed on the first segment. In case of a match in the first segment, the second match line segment is selectively precharged and searching proceeds to the second segment. If there is a match in the second segment, a third segment is precharged and searching proceeds in a similar manner until all segments of a match line have been searched. Precharging of a subsequent segment therefore only occurs in case of a match result in a previous segment. In the case of a match in all segments, selective precharging each segment to a logic xe2x80x98Hxe2x80x99 however still requires a large current. Furthermore, a significant delay is introduced in the search time by having to wait for the selective precharge to occur in a segment before proceeding with the actual comparison in that segment.
U.S. Pat. No. 6,191,970 (Pereira) a match line is divided into multiple segments all of which are simultaneously precharged to a logic xe2x80x98Hxe2x80x99 state prior to beginning a search operation. In addition, each CAM cell has an associated discharge circuit for selectively discharging its corresponding match line segment in response to a disable signal from a previous match line segment. A segment therefore is only discharged if the immediately preceding segment results in a miss while all subsequent segments remain precharged to a logic xe2x80x98Hxe2x80x99. As a result, the miss condition of one segment is propagated along the remainder of the row without discharging all other segments along the row. While this approach alleviates the problem of delays introduced by selectively precharging segments, the potential for high current consumption still remains, since all match lines must first be precharged to a logic xe2x80x98Hxe2x80x99 state. In addition, the match detect of each segment must be synchronized to a clock signal, clocked since the match line precharges to a hit. As a result, either a number of internal clocks must be generated, or the system clock must be used which increases system latency. Finally, in order to prevent discharge before the segment is enabled a series coupled device is added to each CAM cell, thereby increasing chip area and slowing down the entire operation.
In an article entitled xe2x80x9cUse of Selective Precharge for Low Power on the Match Lines of Content Addressable Memoriesxe2x80x9d by Zukowski et al. IEEE 1997 there is described a method whereby a small segment of an overall match line is precharged and used to perform a partial comparison first and only if a match occurs in that first small segment is the remaining segment of the match line precharged and eventually searched. The article also suggests that theoretically the selective precharge technique could be extended to cover more than one stage, but the additional overhead, extra clock phases and additional buffering would not provide any large additional gains over the single stage selective precharge proposed therein. This approach does not consider the possibility of having multiple match line segments working sequentially but independently of clock cycles, providing a sufficiently fast process technology is available to implement the necessary circuitry. Furthermore, the approach discussed by Zukowski et al. still relies on a precharge to a logic xe2x80x98Hxe2x80x99 state which can draw large amounts of current as previously explained.
Thus there is still a need for a CAM which is capable of consuming less power during search operations than conventional search techniques.
In accordance with the present invention there is provided a method for selectively enabling, during a search operation, at least one of a plurality of matchline segments within a row of a content addressable memory (CAM) array, each matchline segment having a plurality of CAM cells coupled thereto, the method comprising the steps of:
(a) setting the matchline segments to a first search result condition;
(b) evaluating a first matchline segment for a second search result condition; and
(c) selectively enabling a second match line segment, in response to the second search result condition in the first matchline segment, so that said second search result condition can be detected thereat.
In accordance with another aspect of the invention there is provided a content addressable memory (CAM) including a plurality of rows, each of the rows comprising:
(a) a plurality of matchline segments having a plurality of CAM cells coupled thereto;
(b) a circuit for precharging the matchline segments to a first search result condition (miss);
each said segment including:
(i) a sense circuit for detecting a second result condition(hit) therein; and
(ii) a circuit for enabling a discharge path in a subsequent segment, to detect said second search result condition therein(match).